/* 801. 使序列递增的最小交换次数 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
/* 
    动态规划
    每次只能交换相同位置的两个数，所以位置i一定至少满足以下之一
    1.nums1[i] > nums1[i-1] && nums2[i] > nums2[i-1]
    2.nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]


    dp[i][0] 表示位置i为止使数组nums1和nums2满足严格递增且位置i不进行交换的最小操作数
    dp[i][1] 表示位置i为止使数组nums1和nums2满足严格递增且位置i进行交换的最小操作数
    1.当只满足上述情况1而不满足情况2时 位置i的交换情况需要和i-1的情况保持一致
    {
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1] + 1
    }
    2.当只满足上述情况2而不满足情况1时，位置i的交换情况需要和 i-1的情况相反:
    {
        dp[i][0] = dp[i-1][1]
        dp[i][1] = dp[i-1][0] + 1
    }
    3.当同时满足情况1和情况2时，dp[i][0],dp[i][1]取两种情况较小值即可
    {
        dp[i][0] = min(dp[i-1][0],dp[i-1][1])
        dp[i][1] = min(dp[i-1][1],dp[i-1][0]) + 1
    }
*/
var minSwap = function (nums1, nums2) {
	const n = nums1.length
	let a = 0,
		b = 1
	for (let i = 1; i < n; i++) {
		let at = a,
			bt = b
		a = b = n
		if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
			a = Math.min(a, at)
			b = Math.min(b, bt + 1)
		}
		if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
			a = Math.min(a, bt)
			b = Math.min(b, at + 1)
		}
	}
	return Math.min(a, b)
}
